package targetOffer;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 剑指offer全解
 *
 * @author cquxcm
 */
public class TargetOffer {

    /**
     * 第1题
     * <p>
     * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
     * 每一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，
     * 判断数组中是否含有该整数。
     * <p>
     * 分析：
     * 数组中可能是有重复数字的，要充分利用每一行每一列都是递增的这个规律
     * <p>
     * 暴力解法 O(n^2)
     * 一般解法 O(nlogn):对每一行使用二分查找。
     * 较优解法O(n+m)：
     *
     * @param target
     * @param array
     * @return 本题解法：
     * 首先二分查找找出一个目标行，然后在对该行进行二分查找，查找的结果会将整个矩阵分为两个子矩阵，
     * 再分别对这两个子矩阵递归查找。
     * 时间复杂度：O(logn * logm)
     * <p>
     * 测试例子：
     * 1  2  5  9  10
     * 3  6  10 11 12
     * 5  7  12 14 16
     * 8  9  14 16 20
     * @see TargetOffer#isTargetInPartSortArray2(int, int[][])
     */
    public static boolean isTargetInPartSortArray1(int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }

        int h = array.length - 1;
        int w = array[0].length - 1;

        // 根据最大最小值排除
        if (array[0][0] > target || array[h][w] < target) {
            return false;
        }

        return Algorithm.binarySearchIn2DArray(array, target, 0, h, 0, w);
    }

    /**
     * 从左下角开始遍历，如果当前值比target小则往上找，如果比target大则往右找，是一个线性查找个过程
     * <p>
     * 时间复杂度：O(n+m)
     *
     * @param target
     * @param array
     * @return
     */

    public static boolean isTargetInPartSortArray2(int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }

        int h = array.length - 1;
        int w = array[0].length - 1;

        // 根据最大最小值排除
        if (array[0][0] > target || array[h][w] < target) {
            return false;
        }

        int i = h;
        int j = 0;

        while (i >= 0 && j <= w) {
            if (array[i][j] == target) {
                return true;
            } else if (array[i][j] > target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }

    /**
     * 第2题
     * <p>
     * 请实现一个函数，将一个字符串中的每个空格替换成“%20”。
     * 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
     * <p>
     * 解法：通过StringBuilder来辅助构造
     * 时间复杂度：0(n)
     * 空间复杂度：O(n)
     *
     * @param str
     * @return
     */
    public static String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        return Algorithm.replace(str.toString(), ' ', "%20");
    }

    /**
     * 第3题
     * <p>
     * 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
     * <p>
     * 解法：
     * 利用stack或者递归，二者本质一样的
     * <p>
     * 时间复杂度：O(n)
     *
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        if (listNode == null) {
            return list;
        }
        return Algorithm.parseListFromTailToHead(listNode, list);
    }

    /**
     * 第4题
     * <p>
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
     * <p>
     * 解法：本地主要考察递归调用
     * 关键点是找到每个子树对应的前序遍历结果和中序遍历结果，递归地调用即可
     *
     * @param pre 前序遍历结果
     * @param in  中序遍历结果
     * @return 根节点
     */
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length == 0) {
            return null;
        }
        return Algorithm.buildTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    /**
     * 第5题
     * <p>
     * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
     * <p>
     * 队列特点：先进先出
     * <p>
     * 解法：一个栈用于入列，一个栈用于出列
     */
    static class ListImplementWithStack {
        Stack<Integer> stack1 = new Stack<Integer>();//用于保存入列结果
        Stack<Integer> stack2 = new Stack<Integer>();//用于出列

        public void push(int node) {
            stack1.push(node);
        }

        public int pop() {
            if (stack2.size() > 0) {
                return stack2.pop();
            } else {
                while (stack1.size() > 0) {
                    stack2.push(stack1.pop());
                }
                if (stack2.size() > 0) {
                    return stack2.pop();
                }
            }
            throw new IndexOutOfBoundsException();
        }
    }


    /**
     * 第6题
     * <p>
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
     * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
     * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
     * <p>
     * 分析：
     * a----b
     *       c----d
     * <p>
     * 旋转以后数组分为a-b,c-d两段,c-d长度有可能为0,并且有c <= d <= a <= b的关系
     * <p>
     * 解法：
     * 使用二分法查找c，如果i>=a，前边往中间移，否则(此时i>=c)，后边往中间移。
     * i最终的结果是b或者c。
     * 如果i是数组的最后一个，说明，c-d段长度为0,直接返回array[0]
     * 如果i <= d，说名找到的是c，直接返回
     * 否则，找到的是b，它的下一个就是c
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 测试case：
     * {6501, 6828, 6963, 7036, 7422, 7674, 8146, 8468, 8704, 8717, 9170, 9359, 9719, 9895, 9896, 9913,
     * 9962, 154, 293, 334, 492, 1323, 1479, 1539, 1727, 1870, 1943, 2383, 2392, 2996, 3282, 3812, 3903,
     * 4465, 4605, 4665, 4772, 4828, 5142, 5437, 5448, 5668, 5706, 5725, 6300, 6335}
     * {}
     * {1}
     * {1, 2, 3, 4}
     * {2, 3, 1, 4}
     * {1, 2, 3, 1}
     * {1, 1, 1, 1}
     * {3, 2, 2, 2}
     *
     * @param array
     * @return
     */
    public static int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int start = 0;
        int end = array.length - 1;
        int i = 0;

        //查找c
        while (start < end - 1) {
            i = (start + end) / 2;
            if (array[i] >= array[start]) {
                start = i;
            } else {
                end = i;
            }
            if (array[start] < array[end]) {
                break;
            }
        }
        if (i == array.length - 1) {
            return array[0];
        }
        if (array[i] <= array[array.length - 1]) {
            return array[i];
        }
        return array[i + 1];
    }


    /**
     * 第7题
     *
     * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
     *
     * 解法：
     * 避免使用递归，化递归为迭代
     *
     * @param n
     * @return
     */
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            int i = 0;
            int j = 1;
            while (n > 1) {
                j = i + j;
                i = j - i;
                n--;
            }
            return j;
        }
    }

    /**
     * 第8题
     *
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     *
     * 传统解法：使用动态规划,如下
     *
     * 实际上，这题就是求斐波那契数列的第n项，参考上面第7题，不过不同的是f(1) = 1, f(2) = 2
     * @see TargetOffer#fibonacci
     *
     */

    private static class JumpFloor{

        private static int[] cache;

        public static int jumpFloor(int target) {
            if (target <= 0) {
                return 0;
            } else if (target == 1) {
                return 1;
            } else if (target == 2) {
                return 2;
            }else {
                if (cache == null) {
                    cache = new int[target + 1];
                    for (int i = 0; i < cache.length; i++) {
                        cache[i] = -1;
                    }
                }
                if (cache[target] == -1) {
                     // target的值还没计算过
                    cache[target] = jumpFloor(target - 1) + jumpFloor(target - 2);
                }
                return cache[target];
            }
        }
    }

    /**
     * 第9题
     *
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     *
     * 分析：
     * f(1) = 1
     * f(2) = f(1) + 1
     * f(3) = f(1) + f(2) + 1 = 2f(2)
     * f(4) = f(1) + f(2) + f(3) + 1 = 2f(3)
     * ...
     * f(n) = 2f(n-1)
     * f(n) = 2^(n-1)
     *
     * @param target
     * @return
     */
    public static int JumpFloorII(int target) {
        if (target <= 0) {
            return 0;
        } else {
            return Algorithm.pow(2, target - 1);
        }
    }

    /**
     * 第10题
     *
     * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
     * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
     *
     *
     * @param target
     * @return
     */
    public static int rectCover(int target) {
        if (target <= 0) {
            return target;
        } else if (target == 1) {
            return 1;
        } else if (target == 2) {
            return 2;
        } else {
            return rectCover(target - 1) + 2 * rectCover(target - 2);
        }
    }



    public static void main(String[] args) {
        System.out.print(rectCover(5));
    }
}
